/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package hoja7;

/**
 *
 * @author luisorozco
 */

// clase copiada del libro de JavaStruture


import java.util.Vector;

public class PriorityQueue<T> extends QueueAbstract<T> {
    
    protected Vector<T> data; // the data, kept in heap order
    protected int count;
    
    public PriorityQueue() 
    // post: constructs a new priority queue
    {
        data = new Vector<T>();
        count = 0;
    }
    
    protected static int parent(int i) 
    // pre: 0 <= i < size
    // post: returns parent of node at location i
    {
        return (i - 1) / 2;
    }

    protected static int left(int i) 
    // pre: 0 <= i < size
    // post: returns index of left child of node at location i
    {
        return 2 * i + 1;
    }

    protected static int right(int i) 
    // pre: 0 <= i < size
    // post: returns index of right child of node at location i
    {
        return 2 * (i + 1);
    }
    
    protected void percolateUp(int leaf) 
    // pre: 0 <= leaf < size
    // post: moves node at index leaf up to appropriate position
    {
        int parent = parent(leaf);
        Comparable<T> value = (Comparable<T>)data.get(leaf);
        while (leaf > 0 && (value.compareTo(data.get(parent)) < 0)) {
            data.set(leaf, data.get(parent));
            leaf = parent;
            parent = parent(leaf);
        }
        data.set(leaf, (T)value);
    }
    
    @Override
    public void add(T value) 
    // pre: value is non-null comparable
    // post: value is added to priority queue
    {
        count++;
        data.add(value);
        percolateUp(data.size() - 1);
    }
    
    protected void pushDownRoot(int root) 
    // pre: 0 <= root < size
    // post: moves node at index root down
    // to appropriate position in subtree
    {
        int heapSize = data.size();
        T value = data.get(root);
        while (root < heapSize) {
            int childpos = left(root);
            if (childpos < heapSize) {
                if ((right(root) < heapSize)
                        && (((Comparable<T>)data.get(childpos + 1)).compareTo(data.get(childpos)) < 0)) {
                    childpos++;
                }
                // Assert: childpos indexes smaller of two children
                if (((Comparable<T>)data.get(childpos)).compareTo(value) < 0) {
                    data.set(root, data.get(childpos));
                    root = childpos; // keep moving down
                } else { // found right location
                    data.set(root, value);
                    return;
                }
            } else { // at a leaf! insert and halt
                data.set(root, value);
                return;
            }
        }
    }
    
    @Override
    public T poll() 
    // pre: !isEmpty()
    // post: returns and removes minimum value from queue
    {
        if(isEmpty()) {
            return null;
        } else {
            count--;
            T minVal = data.get(0);
            data.set(0, data.get(data.size() - 1));
            data.setSize(data.size() - 1);
            if (data.size() > 1) {
                pushDownRoot(0);
            }
            return minVal;
        }        
    }
    
    @Override
    public int size()
    // post: returns number of elements in list
    {
        return count;
    }

    @Override
    public boolean isEmpty() 
    // post: returns true if the list is empty
    {
        return 0 == count;   
    }
}